눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.
첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.
스택을 이용한 DFS를 수행하고, 각 영역을 저장하기 위해 ArrayList를 사용합니다.
Method | Return | Description |
---|---|---|
Solution(M, N) | - | 영역 전체 크기를 입력 받아 저장하는 생성자 |
solution(int[][] arr) | - | 직사각형의 좌표를 입력 받고, DFS 수행으로 영역의 개수와 각 넓이를 출력 |
setBlock(int lx, int ly, int rx, int ry) | - | 직사각형으로 덮히는 부분을 표시 |
DFS() | ArrayList<Integer > |
깊이 우선 탐색을 하며 나눠진 영역의 넓이를 ArrayList에 저장한 후 반환 |
이전에 풀었던 DFS 문제와 비슷한 유형인데 각각의 넓이를 구하는 연산이 추가된 응용 문제입니다. 어렵지 않게 풀 수 있습니다.
사용 연어: Java 11
메모리 | 시간 |
16236 KB | 176 ms |
감사합니다.
Text by Chaelin. Photographs by Chaelin, Unsplash.